package Hot100;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2021-12-29 12:01
 *
 * 只出现一次的数字==某个元素出现m次，其他元素均出现n次，找出出现m次的元素
 * 通用方法：使用Map记录每个元素出现的次数，然后找到只出现1次的返回即可
 *
 * 136. 只出现一次的数字---m=1,n=2
 * 540. 有序数组中的单一元素--m=1,n=2 有序
 * 137 只出现一次的数字(剑指 Offer II 004,剑指 Offer 56 - II. ) II--m=1,n=3
 * 260 只出现一次的数字 III--m=1,n=2,有两个m出现1次
 * 169. 多数元素(剑指 Offer 39. 数组中出现次数超过一半的数字)
 * NC156 数组中只出现一次的数（其它数出现k次）---m=1,n=k
 */
public class singleNumber136 {
    /**
     * 136. 只出现一次的数字
     * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     * 1、map记录元素个数
     * 2、全部异或操作得到的结果就是
     * 3、排序，挨个与前一个元素判断
     * */
    public int singleNumber1(int[] nums) {
        int res=0;
        for (int num:nums) {
            res^=num;
        }
        return res;
    }

    /**
     * 540. 有序数组中的单一元素
     * 给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。请你找出并返回只出现一次的那个数。
     * 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
     * 1、全部异或
     * 2、判断奇数为的元素，比较其与前一个元素是否相等即可
     * 3、二分查找：整个数组一定是奇数个元素
     *    halvesAreEven = (hi - mid) % 2 == 0确定中间元素的那一侧的元素个数是奇数，
     *    --1.中间元素与右边元素相同，且mid分两半的数组为偶数，则mid+1后面的右边数组为奇数个元素，left=mid+2
     *    --2.中间元素与右边元素相同，且mid分两半的数组奇数，则mid左边的元素个数为奇数个，right=mid-1；
     *    --3.中间元素与左边元素相同，且mid分两半的数组为偶数，则mid-1前面的左边数组为奇数个，right=mid-2；
     *    --4.中间元素与左边元素相同，且分mid两半的数组为奇数，则mid右边的元素个数为奇数个，left=mid+1；
     * 4、只对偶数索引进行二分搜索，直到遇到第一个其后元素不相同的索引
     * */
    public int singleNonDuplicate1(int[] nums) {
        int n=nums.length;
        if (n==1) return nums[0];
        for (int i = 1; i < n; i+=2) {
            if(nums[i]!=nums[i-1]){
                return nums[i-1];
            }
        }
        return nums[n-1];
    }
    public int singleNonDuplicate2(int[] nums) {
        int n=nums.length;
        int left=0,right=n-1;
        while (left<right){
            int mid=left+(right-left)/2;
            boolean halvesAreEven = (right - mid) % 2==0;
            if (nums[mid]==nums[mid+1]){
                if (halvesAreEven){
                    //1.中间元素与右边元素相同，且mid分两半的数组为偶数，则mid+1后面的右边数组为奇数个元素，left=mid+2
                    left=mid+2;
                }else {
                    //2.中间元素与右边元素相同，且mid分两半的数组奇数，则mid左边的元素个数为奇数个，right=mid-1；
                    right=mid-1;
                }
            }else if (nums[mid]==nums[mid-1]){
                if (halvesAreEven){
                    //3.中间元素与左边元素相同，且mid分两半的数组为偶数，则mid-1前面的左边数组为奇数个，right=mid-2；
                    right=mid-2;
                }else {
                    //4.中间元素与左边元素相同，且分mid两半的数组为奇数，则mid右边的元素个数为奇数个，left=mid+1；
                    left=mid+1;
                }
            }else {
                return nums[mid];
            }
        }
        return nums[left];
    }

    public int singleNonDuplicate(int[] nums) {
        int left=0,right=nums.length-1;
        while (left<right){
            int mid=left+(right-left)/2;
            if (mid%2==1) mid--;
            if (nums[mid]==nums[mid+1]){
                left=mid+2;
            }else {
                right=mid;
            }
        }
        return nums[left];
    }

    /**
     * 137. 只出现一次的数字 II
     * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
     * 位运算：依次判断每个二进制位，考虑答案的第i为可能为0或1，对应非答案的元素，对应着第i为有3个0或1，
     * 因此，对每一位二进制之和除以3取余就是答案的第i为
     * */
    public int singleNumber2(int[] nums) {
        int res=0;
        for (int i = 0; i < 32; i++) {
            int total=0;
            for (int num:nums) {
                total+=(num>>i)&1;
            }
            if (total%3!=0){
                res|=1<<i;
            }
        }
        return res;
    }

    /**
     * 260. 只出现一次的数字 III
     * 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
     * 位运算，先将所有元素异或，得到的结果即为两个答案的异或结果，根据这个结果找到结果中第一个不为0的二进制位index，这一位可以区分两个元素
     * 然后再遍历整个数组，将其分为两份，按照这个index的不同，可以发现：
     * 对于不是答案的其他元素，会将两次出现包含在同一组
     * 对于是答案的两个元素，一定会分在两个不同的组
     * */
    public int[] singleNumber(int[] nums) {
        int xorSum=0;
        for (int num:nums) {
            xorSum^=num;
        }
        int index=1;
        while ((index&xorSum)==0){
            //每次左移一位，然后与xorSum与操作得到从后向前的每一位值
            index<<=1;
        }
        int a=0,b=0;
        for (int num:nums) {
            if ((index&num)==0){
                a^=num;
            }else {
                b^=num;
            }
        }
        return new int[]{a,b};
    }

    /**
     * 剑指 Offer 39. 数组中出现次数超过一半的数字
     * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * 1、排序后，中间位置的元素即为答案
     * */
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

    /**
     * NC156 数组中只出现一次的数（其它数出现k次）
     * 给定一个长度为 n 的整型数组 arr 和一个整数 k(k>1) 。已知 arr 中只有 1 个数出现一次，其他的数都出现 k 次。请返回只出现了 1 次的数。
     * 排序后，遍历k的倍数的下标
     * */
    public int foundOnceNumber (int[] arr, int k) {
        Arrays.sort(arr);
        for (int i = 0; i < arr.length-1; i++) {
            if (arr[i]==arr[i+1]){
                i+=k-1;
            }else {
                return arr[i];
            }
        }
        return arr[arr.length-1];
    }
}
